package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/
https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html

530. 二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

示例 1：
输入：root = [4,2,6,1,3]
输出：1

示例 2：
输入：root = [1,0,48,null,null,12,49]
输出：1
 */
class leetcode_530 {
    @Test
    fun test_1() {
        val root = TreeNode(4)
        val n2 = TreeNode(2)
        val n6 = TreeNode(6)
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        root.left = n2
        root.right = n6
        n2.left = n1
        n3.right = n3

        val actual = getMinimumDifference(root)
        val expect = 1
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val root = TreeNode(1)
        val n0 = TreeNode(0)
        val n12 = TreeNode(12)
        val n48 = TreeNode(48)
        val n49 = TreeNode(49)
        root.left = n0
        root.right = n48
        n48.left = n12
        n48.right = n49

        val actual = getMinimumDifference(root)
        val expect = 1
        Assert.assertEquals(expect, actual)
    }

    fun getMinimumDifference(root: TreeNode?): Int {
        // 中序遍历
        // getMinimumDifference1(root)
        // return min
        return getMinimumDifference2(root)
    }

    var min: Int = Int.MAX_VALUE
    var prev: TreeNode? = null
    fun getMinimumDifference1(root: TreeNode?) {
        /**
         * 题型：中序遍历
         *
         * 思路：
         * 题目中的数都是正数，因此最小差值一定是相邻节点的，从左下角开始遍历。
         * 用 prev 指针 记录上一个节点。
         * 用 prev 节点与当前节点 得到 节点差值， 节点差值 与 min 的最小值，就是新的min
         *
         * 时间复杂度：O(N)
         *
         * 空间复杂度：O(H)
         */
        // 中序遍历 - 递归 + 双指针方（pre，当前节点）
        // T - N
        // S - 1

        // 终止条件
        if (null == root) {
            return
        }

        // 左
        root.left?.let {
            getMinimumDifference1(it)
        }

        // 中
        prev?.let {
            min = Math.min(min, Math.abs(root.`val` - it.`val`))
        }
        prev = root
        // 递归伴随着回溯过程

        // 右
        root.right?.let {
            getMinimumDifference1(it)
        }
    }

    fun getMinimumDifference2(root: TreeNode?): Int {
        // 中序遍历 - 迭代　+ 双指针法
        // T - N
        // S - N
        if (null == root) {
            return -1
        }
        // 栈 - 右中左
        var pre: TreeNode? = null
        var min: Int = Int.MAX_VALUE
        val stack: LinkedList<Pair<TreeNode, Boolean>> = LinkedList<Pair<TreeNode, Boolean>>()
        stack.push(Pair<TreeNode, Boolean>(root, false))

        while (!stack.isEmpty()) {
            val pair: Pair<TreeNode, Boolean> = stack.pop()
            val node: TreeNode = pair.first
            val visited: Boolean = pair.second

            if (visited) {
                if (null != pre) {
                    min = Math.min(min, Math.abs(pre.`val` - node.`val`))
                }
                pre = node
                continue
            }

            // 右
            node.right?.let {
                stack.push(Pair<TreeNode, Boolean>(it, false))
            }

            // 中
            stack.push(Pair<TreeNode, Boolean>(node, true))

            // 左
            node.left?.let {
                stack.push(Pair<TreeNode, Boolean>(it, false))
            }

        }
        return min
    }
}